class Solution {
public:
    string getSmallestString(string s)
    {
        string ans;
        int n = s.size();
        int i = 0, j = 1;
        while (i < n && j < n)
        {
            if ((((s[i] - '0') % 2 == 0 && (s[j] - '0') % 2 == 0) && s[i] > s[j]) || (((s[i] - '0') % 2 == 1 && (s[j] - '0') % 2 == 1) && s[i] > s[j]))
            {
                swap(s[i], s[j]);
                i = j + 1, j += 1;
            }
            else i += 1, j += 1;
        }
        return s;
    }
};